Search Results

Documents authored by Laumanns, Marco

Document
DOI: 10.4230/OASIcs.ATMOS.2014.15
Shortest Path with Alternatives for Uniform Arrival Times: Algorithms and Experiments

Authors: Tim Nonner and Marco Laumanns

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)

Abstract
The Shortest Path with Alternatives (SPA) policy differs from classical shortest path routing in the following way: instead of providing an exact list of means of transportation to follow, this policy gives such a list for each stop, and the traveler is supposed to pick the first option from this list when waiting at some stop. First, we show that an optimal policy of this type can be computed in polynomial time for uniform arrival times under reasonable assumptions. A similar result was so far only known for Poisson arrival times, which are less realistic for frequency-based public transportation systems. Second, we experimentally evaluate such policies. In this context, our main finding is that SPA policies are surprisingly competitive compared to traditional shortest paths, and moreover yield a significant reduction of waiting times, and therefore improvement of user experience, compared to similar greedy approaches. Specifically, for roughly 25% of considered cases, we could decrease the expected waiting time by at least 20%. To run our experiments, we also describe a tool-chain to derive the necessary information from the popular GTFS-format, therefore allowing the application of SPA policies to a wide range of public transportation systems.
Cite as

Tim Nonner and Marco Laumanns. Shortest Path with Alternatives for Uniform Arrival Times: Algorithms and Experiments. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 15-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{nonner_et_al:OASIcs.ATMOS.2014.15,
  author =	{Nonner, Tim and Laumanns, Marco},
  title =	{{Shortest Path with Alternatives for Uniform Arrival Times: Algorithms and Experiments}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{15--24},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.15},
  URN =		{urn:nbn:de:0030-drops-47494},
  doi =		{10.4230/OASIcs.ATMOS.2014.15},
  annote =	{Keywords: Shortest Path, Stochastic Optimization, Public Transportation}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2007.1173
09. Periodic Railway Timetabling with Event Flexibility

Authors: Gabrio Curzio Caimi, Martin Fuchsberger, Marco Laumanns, and Kaspar Schüpbach

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)

Abstract
This paper addresses the problem of generating conflict-free periodic train schedules for large railway networks. We follow a two level approach, where a simplified track topology is used to obtain a macro level schedule and the detailed topology is considered locally on the micro level. To increase the solution space in the interface of the two levels, we propose an extension of the well-known Periodic Event Scheduling Problem (PESP) such that it allows to generate flexible time slots for the departure and arrival times instead of exact times. This Flexible Periodic Event Scheduling Problem (FPESP) formulation considerably increases the chance to obtain feasible solutions (exact train routings) subsequently on the micro level, in particular for stations with dense peak traffic. Total trip time and the time slot sizes are used as multiple objectives and weighted and/or constrained to allocate the flexibility where it is most useful. Tests on an instance of the 2007 service intention of the Swiss Federal Railways demonstrate the advantage of the FPESP model, while it only moderate increases its solution time in most cases.
Cite as

Gabrio Curzio Caimi, Martin Fuchsberger, Marco Laumanns, and Kaspar Schüpbach. 09. Periodic Railway Timetabling with Event Flexibility. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 124-141, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{caimi_et_al:OASIcs.ATMOS.2007.1173,
  author =	{Caimi, Gabrio Curzio and Fuchsberger, Martin and Laumanns, Marco and Sch\"{u}pbach, Kaspar},
  title =	{{09. Periodic Railway Timetabling with Event Flexibility}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{124--141},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1173},
  URN =		{urn:nbn:de:0030-drops-11735},
  doi =		{10.4230/OASIcs.ATMOS.2007.1173},
  annote =	{Keywords: }
}
Document
DOI: 10.4230/DagSemProc.04461.6
An Adaptive Scheme to Generate the Pareto Front Based on the Epsilon-Constraint Method

Authors: Marco Laumanns, Lothar Thiele, and Eckart Zitzler

Published in: Dagstuhl Seminar Proceedings, Volume 4461, Practical Approaches to Multi-Objective Optimization (2005)

Abstract
We discuss methods for generating or approximating the Pareto set of multiobjective optimization problems by solving a sequence of constrained single-objective problems. The necessity of determining the constraint value a priori is shown to be a serious drawback of the original epsilon-constraint method. We therefore propose a new, adaptive scheme to generate appropriate constraint values during the run. A simple example problem is presented, where the running time (measured by the number of constrained single-objective sub-problems to be solved) of the original epsilon-constraint method is exponential in the problem size (number of decision variables), although the size of the Pareto set grows only linearly. We prove that --- independent of the problem or the problem size --- the time complexity of the new scheme is O(k^{m-1}), where k is the number of Pareto-optimal solutions to be found and m the number of objectives. Simulation results for the example problem as well as for different instances of the multiobjective knapsack problem demonstrate the behavior of the method, and links to reference implementations are provided.
Cite as

Marco Laumanns, Lothar Thiele, and Eckart Zitzler. An Adaptive Scheme to Generate the Pareto Front Based on the Epsilon-Constraint Method. In Practical Approaches to Multi-Objective Optimization. Dagstuhl Seminar Proceedings, Volume 4461, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{laumanns_et_al:DagSemProc.04461.6,
  author =	{Laumanns, Marco and Thiele, Lothar and Zitzler, Eckart},
  title =	{{An Adaptive Scheme to Generate the Pareto Front Based on the Epsilon-Constraint Method}},
  booktitle =	{Practical Approaches to Multi-Objective Optimization},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4461},
  editor =	{J\"{u}rgen Branke and Kalyanmoy Deb and Kaisa Miettinen and Ralph E. Steuer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04461.6},
  URN =		{urn:nbn:de:0030-drops-2465},
  doi =		{10.4230/DagSemProc.04461.6},
  annote =	{Keywords: Multiple objective optimization, non-dominated set, Pareto set, epsilon-constraint method, generating methods}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact